public class ReverseBetween {
    // newcoder 链表内指定区间反转
    // https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode leftHead = null, leftTail = null, midHead = null ,midTail = null, rightHead = null, rightTail = null;
        int index = 1;
        ListNode cur = head, prev = null;
        while (cur != null) {
            if (index < m) {
                if (leftHead == null) {
                    leftHead = cur;
                }
                leftTail = cur;
                cur = cur.next;
            }else if (index >= m && index <= n) {
                if (index == m) {
                    midHead = cur;
                }
                if (index == n) {
                    midTail = cur;
                }
                ListNode nextCur = cur.next;
                cur.next = prev;
                prev = cur;
                cur = nextCur;
            }else {
                if (rightHead == null) {
                    rightHead = cur;
                }
                rightTail = cur;
                cur = cur.next;
            }
            index++;
        }
        if (leftHead != null) {
            leftTail.next = midTail;
        }
        if (rightHead != null) {
            midHead.next = rightHead;
        }
        return leftHead == null ? midTail : leftHead;
    }

    public static void main(String[] args) {
        ReverseBetween reverseBetween = new ReverseBetween();
        ListNode head = new ListNode(3);
        head.next = new ListNode(5);
        reverseBetween.reverseBetween(head, 1,2);
    }
}
